package com.company.linked;

import com.company.ListNode;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/partition-list/
 * @date 2019/11/20 16:18
 * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 *
 * 你应当保留两个分区中每个节点的初始相对位置。
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5
 */
public class PartitionList {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);

        ListNode listNode = partition(head, 3);

    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode head01 = new ListNode(-1);
        ListNode head02 = new ListNode(-1);
        ListNode p1 = head01;
        ListNode p2 = head02;
        ListNode p = head;

        while (p != null) {
            if (p.val < x) {
                p1.next = new ListNode(p.val);
                p1 = p1.next;

            }else {
                p2.next = new ListNode(p.val);
                p2 = p2.next;
            }
            p = p.next;
        }

        p1.next = head02.next;
        return head01.next;
    }

}
